package com.explorati.LeetCode94.inorderTraversal;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 21:35 2020/9/19 0019
 * @ Description ：中序遍历(非递归解法)
 */
public class Solution1 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 给定一个二叉树，返回它的中序 遍历
     * 思路：每到一个节点 A，因为根的访问在中间，将 A 入栈。然后遍历左子树，接着访问 A，最后遍历右子树。
     *
     * 在访问完 A 后，A 就可以出栈了。因为 A 和其左子树都已经访问完成。
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();

        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            //如果当前节点不为null，访问其左节点，将其放入栈中直至没有左节点
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //当左节点全部访问完成后，访问左叶子节点
            cur = stack.pop();
            //将其放入res中
            res.add(cur.val);
            //替换下面的四行代码，否则时间性能过不去
            cur = cur.right;
            //如果当前访问的节点有右节点，将其放入栈中
//            if(cur.right != null) {
//                stack.push(cur.right);
//            }
//            cur = stack.pop();

        }
        return res;
    }
}

